package leetcode.array;

import leetcode.Hot100.canJump;

/**
 * @author Cheng Jun
 * Description: 在 leetcode.Hot100.canJump 基础上，假设你总是可以到达数组的最后一个位置，要求次数最少。
 * @version 1.0
 * @date 2022/7/19 14:07
 * @see canJump
 */
public class canJump1 {

    static int jump(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        // [2, 1, 1]
        // 在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，
        // 我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，
        // 在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
        // 链接：https://leetcode.cn/problems/jump-game-ii/solution/tiao-yue-you-xi-ii-by-leetcode-solution/
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }
}
